package leetcode;

/**
 * Created by Ghost on 2014/11/15.
 */
public class Decode_Ways {
    public int numDecodings(String s) {
        if(s==null || s.isEmpty() ||s.charAt(0)=='0')
            return 0;
        char[] str = s.toCharArray();
        if(str.length==1)
            return str[0]=='0'?0:1;
        int[] w = new int[str.length + 1];
        w[0] = 1;
        w[1] = str[1]=='0'?0:1;
        for (int i=2;i<w.length;i++){
            char cur = str[i-1];
            int alone = 0;
            int dbl = 0;
            int rst = 0;
            if(cur!='0')
                alone = 1;
            int twoNum = Integer.parseInt(""+str[i-2]+cur);
            if(str[i-2]!='0' && twoNum>=1 && twoNum<=26){
                dbl = 1;
            }
            rst = alone*w[i-1]+dbl*w[i-2];
            w[i] = rst;
        }
        return w[w.length-1];
    }
    public static void main(String[] args){
        Decode_Ways decode_ways = new Decode_Ways();

        String a = "4757562545844617494555774581341211511296816786586787755257741178599337186486723247528324612117156948";
        System.out.println(decode_ways.numDecodings(a));
    }
}
